SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bucket queue</title>

</head>

Bucket queue

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Bucket queue</th></tr><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">An array of buckets, suitable for priorities in the range from 1 to 6. The minimum-priority element can be found in the leftmost non-empty bucket.</div></td></tr><tr><th scope="row" class="infobox-label"><a href="List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data"><a href="Priority_queue" title="Priority queue">priority queue</a></td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1969</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data">Robert Dial</td></tr><tr><td colspan="2" class="infobox-full-data"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="Time_complexity" title="Time complexity">Time complexity</a> in <a href="Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a">

Average</td><td class="infobox-data infobox-data-b">

Worst case</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a">

O(1)</td><td class="infobox-data infobox-data-b">

O(1)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Find-min</th><td class="infobox-data infobox-data-a">

O(#priorities)</td><td class="infobox-data infobox-data-b">

O(#priorities)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete-min</th><td class="infobox-data infobox-data-a">

O(#priorities)</td><td class="infobox-data infobox-data-b">

O(#priorities)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Decrease-key</th><td class="infobox-data infobox-data-a">

O(1)</td><td class="infobox-data infobox-data-b">

O(1)</td></tr><tr><th colspan="4" class="infobox-header"><a href="Space_complexity" title="Space complexity">Space complexity</a></th></tr></tbody></table></td></tr></tbody></table>

A bucket queue is a <a href="Data_structure" title="Data structure">data structure</a> that implements the <a href="Priority_queue" title="Priority queue">priority queue</a> <a href="Abstract_data_type" title="Abstract data type">abstract data type</a>: it maintains a dynamic collection of elements with numerical priorities and allows quick access to the element with minimum (or maximum) priority. In the bucket queue, the priorities must be <a href="Integer" title="Integer">integers</a>, and it is particularly suited to applications in which the priorities have a small range.<a href="#cite_note-skiena-1">[1]</a> A bucket queue has the form of an array of buckets: an <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array data structure</a>, indexed by the priorities, whose cells contain <a href="Container_(abstract_data_type)" title="Container (abstract data type)">collections of items</a> with the same priority as each other. With this data structure, insertion of elements and changes of their priority take <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a>. Searching for and removing the minimum-priority element takes time proportional to the number of buckets or, by maintaining a pointer to the most recently found bucket, in time proportional to the difference in priorities between successive operations.

The bucket queue is the priority-queue analogue of <a href="Pigeonhole_sort" title="Pigeonhole sort">pigeonhole sort</a> (also called bucket sort), a sorting algorithm that places elements into buckets indexed by their priorities and then concatenates the buckets. Using a bucket queue as the priority queue in a <a href="Selection_sort" title="Selection sort">selection sort</a> gives a form of the pigeonhole sort algorithm.<a href="#cite_note-figueira-2">[2]</a> Bucket queues are also called bucket priority queues<a href="#cite_note-hns-3">[3]</a> or bounded-height priority queues.<a href="#cite_note-skiena-1">[1]</a> When used for quantized approximations to <a href="Real_number" title="Real number">real number</a> priorities, they are also called untidy priority queues<a href="#cite_note-remarks-4">[4]</a> or pseudo priority queues.<a href="#cite_note-pseudo-5">[5]</a> They are closely related to the <a href="Calendar_queue" title="Calendar queue">calendar queue</a>, a structure that uses a similar array of buckets for exact prioritization by real numbers.

Applications of the bucket queue include computation of the <a href="Degeneracy_(graph_theory)" title="Degeneracy (graph theory)">degeneracy of a graph</a>, fast <a href="Algorithm" title="Algorithm">algorithms</a> for <a href="Shortest_path" class="mw-redirect" title="Shortest path">shortest paths</a> and <a href="Widest_path_problem" title="Widest path problem">widest paths</a> for graphs with weights that are small integers or are already sorted, and greedy <a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithms</a> for the <a href="Set_cover_problem" title="Set cover problem">set cover problem</a>. The quantized version of the structure has also been applied to <a href="Scheduling_(computing)" title="Scheduling (computing)">scheduling</a><a href="#cite_note-figueira-2">[2]</a> and to <a href="Marching_cubes" title="Marching cubes">marching cubes</a> in <a href="Computer_graphics" title="Computer graphics">computer graphics</a>.<a href="#cite_note-remarks-4">[4]</a> The first use of the bucket queue<a href="#cite_note-es-6">[6]</a> was in a shortest path algorithm by <a href="#CITEREFDial1969">Dial (1969)</a>.<a href="#cite_note-dial-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Operation">Operation</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Basic_data_structure">Basic data structure</h3></div>

A bucket queue can handle elements with integer priorities in the range from 0 or 1 up to some known bound C, and operations that insert elements, change the priority of elements, or extract (find and remove) the element that has the minimum (or maximum) priority. It consists of an array A of <a href="Container_(abstract_data_type)" title="Container (abstract data type)">container data structures</a>; in most sources these containers are <a href="Doubly_linked_list" title="Doubly linked list">doubly linked lists</a> but they could alternatively be <a href="Dynamic_array" title="Dynamic array">dynamic arrays</a><a href="#cite_note-hns-3">[3]</a> or <a href="Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>. The container in the pth array cell A[p] stores the collection of elements whose priority is p.

A bucket queue can handle the following operations:

<ul><li>To insert an element x with priority p, add x to the container at A[p].</li>

<li>To change the priority of an element, remove it from the container for its old priority and re-insert it into the container for its new priority.</li>

<li>To extract an element with the minimum or maximum priority, perform a <a href="Sequential_search" class="mw-redirect" title="Sequential search">sequential search</a> in the array to find the first or last non-empty container, respectively, choose an arbitrary element from this container, and remove it from the container.</li></ul>

In this way, insertions and priority changes take constant time, and extracting the minimum or maximum priority element takes time O(C).<a href="#cite_note-skiena-1">[1]</a><a href="#cite_note-es-6">[6]</a><a href="#cite_note-ms-8">[8]</a>

<div class="mw-heading mw-heading3"><h3 id="Optimizations">Optimizations</h3></div>

As an optimization, the data structure can start each sequential search for a non-empty bucket at the most recently-found non-empty bucket instead of at the start of the array. This can be done in either of two different ways, lazy (delaying these sequential searches until they are necessary) or eager (doing the searches ahead of time). The choice of when to do the search affects which of the data structure operations is slowed by these searches. Dial's original version of the structure used a lazy search. This can be done by maintaining an index L that is a <a href="Lower_bound" class="mw-redirect" title="Lower bound">lower bound</a> on the minimum priority of any element currently in the queue. When inserting a new element, L should be updated to the minimum of its old value and the new element's priority. When searching for the minimum priority element, the search can start at L instead of at zero, and after the search L should be left equal to the priority that was found in the search.<a href="#cite_note-dial-7">[7]</a><a href="#cite_note-bertsekas-9">[9]</a> Alternatively, the eager version of this optimization keeps L updated so that it always points to the first non-empty bucket. When inserting a new element with a priority smaller than L, the data structure sets L to the new priority, and when removing the last element from a bucket with priority L, it performs a sequential search through larger indexes until finding a non-empty bucket and setting L to the priority of the resulting bucket.<a href="#cite_note-skiena-1">[1]</a>

In either of these two variations, each sequential search takes time proportional to the difference between the old and new values of L. This could be significantly faster than the O(C) time bound for the searches in the un-optimized version of the data structure. In many applications of priority queues such as <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a>, the minimum priorities form a <a href="Monotonic_sequence" class="mw-redirect" title="Monotonic sequence">monotonic sequence</a>, allowing a <a href="Monotone_priority_queue" title="Monotone priority queue">monotone priority queue</a> to be used. In these applications, for both the lazy and eager variations of the optimized structure, the sequential searches for non-empty buckets cover disjoint ranges of buckets. Because each bucket is in at most one of these ranges, their numbers of steps add to at most C. Therefore, in these applications, the total time for a sequence of n operations is O(n + C), rather than the slower O(nC) time bound that would result without this optimization.<a href="#cite_note-bertsekas-9">[9]</a> A corresponding optimization can be applied in applications where a bucket queue is used to find elements of maximum priority, but in this case it should maintain an index that upper-bounds the maximum priority, and the sequential search for a non-empty bucket should proceed downwards from this upper bound.<a href="#cite_note-lmw-10">[10]</a>

Another optimization (already given by <a href="#CITEREFDial1969">Dial 1969</a>) can be used to save space when the priorities are monotonic and, throughout the course of an algorithm, always fall within a range of r values rather than extending over the whole range from 0 to C. In this case, one can index the array by the priorities modulo r rather than by their actual values. The search for the minimum priority element should always begin at the previous minimum, to avoid priorities that are higher than the minimum but have lower moduli. In particular, this idea can be applied in Dijkstra's algorithm on graphs whose edge lengths are integers in the range from 1 to r.<a href="#cite_note-ms-8">[8]</a>

Because creating a new bucket queue involves initializing an array of empty buckets, this initialization step takes time proportional to the number of priorities. A variation of the bucket queue described by <a href="Donald_B._Johnson" title="Donald B. Johnson">Donald B. Johnson</a> in 1981 instead stores only the non-empty buckets in a linked list, sorted by their priorities, and uses an auxiliary search tree to quickly find the position in this linked list for any new buckets. It takes time O(log log C) to initialize this variant structure, constant time to find an element with minimum or maximum priority, and time O(log log D) to insert or delete an element, where D is the difference between the nearest smaller and larger priorities to the priority of the inserted or deleted element.<a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

For example, consider a bucket queue with four priorities, the numbers 0, 1, 2, and 3. It consists of an array <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> whose four cells each contain a collection of elements, initially empty. For the purposes of this example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> can be written as a bracketed sequence of four sets: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}</annotation>

</semantics>

</math><img src="./b03889aace49a9813cb079f486979eac9cdeb546.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.887ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}" loading="lazy">. Consider a sequence of operations in which we insert two elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> with the same priority 1, insert a third element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math><img src="./bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"> with priority 3, change the priority of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

<ul><li>After inserting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> with priority 1, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}</annotation>

</semantics>

</math><img src="./5f8bd01bdf3373288202920d3a11de807ced6340.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.379ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}" loading="lazy">.</li>

<li>After inserting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> with priority 1, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}</annotation>

</semantics>

</math><img src="./6836950ed73ce5759b7e17101fcfbb9977dc5ae0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.568ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}" loading="lazy">.</li>

<li>After inserting z with priority 3, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}</annotation>

</semantics>

</math><img src="./47dc46870ff4dd0ac1aee55747f4342e80995935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.819ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}" loading="lazy">.</li>

<li>Changing the priority of x from 1 to three involves removing it from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[1]}</annotation>

</semantics>

</math><img src="./0101dc327d69a56849150de7139305431f1e3ae4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.199ex; height:2.843ex;" alt="{\displaystyle A[1]}" loading="lazy"> and adding it to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[3]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[3]}</annotation>

</semantics>

</math><img src="./fad3f1cbea6f7cb9b43da98cb6c31e0043e47713.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.199ex; height:2.843ex;" alt="{\displaystyle A[3]}" loading="lazy">, after which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}</annotation>

</semantics>

</math><img src="./aa35cae0268800ac590196fa38bcb10101f311d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.819ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}" loading="lazy">.</li>

<li>Extracting the minimum-priority element, in the basic version of the bucket queue, searches from the start of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> to find its first non-empty element: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[0]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[0]}</annotation>

</semantics>

</math><img src="./38cbd6359dc6dbcfff1b53c12e28aec80b4412c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.199ex; height:2.843ex;" alt="{\displaystyle A[0]}" loading="lazy"> is empty but <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[1]=\{y\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[1]=\{y\}}</annotation>

</semantics>

</math><img src="./7eda973ab0b4a76ca25fefa021d1b922e4a7421f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.778ex; height:2.843ex;" alt="{\displaystyle A[1]=\{y\}}" loading="lazy">, a non-empty set. It chooses an arbitrary element of this set (the only element, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">) as the minimum-priority element. Removing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> from the structure leaves <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}</annotation>

</semantics>

</math><img src="./3fb5cce322141f971191687558d6206e53f2532e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.501ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}" loading="lazy">.</li>

<li>The second extract operation, in the basic version of the bucket queue, searches again from the start of the array: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[0]=\emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[0]=\emptyset }</annotation>

</semantics>

</math><img src="./9041bfcbd1f584305454be57c6ddbadcb7ec1a24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.46ex; height:2.843ex;" alt="{\displaystyle A[0]=\emptyset }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[1]=\emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[1]=\emptyset }</annotation>

</semantics>

</math><img src="./e59ad0750cb313b2cd8bb7dc222e376fa849c927.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.46ex; height:2.843ex;" alt="{\displaystyle A[1]=\emptyset }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[2]=\emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[2]=\emptyset }</annotation>

</semantics>

</math><img src="./4aaef1cbf33cf5fda957556f82f94014149f26ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.46ex; height:2.843ex;" alt="{\displaystyle A[2]=\emptyset }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[3]={}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[3]={}}</annotation>

</semantics>

</math><img src="./2c02cf0500282aa9834aa51c3ed2f1ee95e35c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.298ex; height:2.843ex;" alt="{\displaystyle A[3]={}}" loading="lazy">non-empty. In the improved variants of the bucket queue, this search starts instead at the last position that was found to be non-empty, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[1]}</annotation>

</semantics>

</math><img src="./0101dc327d69a56849150de7139305431f1e3ae4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.199ex; height:2.843ex;" alt="{\displaystyle A[1]}" loading="lazy">. In either case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[3]=\{x,z\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[3]=\{x,z\}}</annotation>

</semantics>

</math><img src="./fe2a9e8185345586e1e8b5159662234b5fe86b6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.074ex; height:2.843ex;" alt="{\displaystyle A[3]=\{x,z\}}" loading="lazy"> is found to be the first non-empty set. One of its elements is chosen arbitrarily as the minimum-priority element; for example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z}</annotation>

</semantics>

</math><img src="./bf368e72c009decd9b6686ee84a375632e11de98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.088ex; height:1.676ex;" alt="{\displaystyle z}" loading="lazy"> might be chosen. This element is removed, leaving <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}</annotation>

</semantics>

</math><img src="./5e5eb620738297effbdfb2fa8daaad3e32a12fd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.379ex; height:2.843ex;" alt="{\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}" loading="lazy">.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Graph_degeneracy">Graph degeneracy</h3></div>

A bucket queue can be used to maintain the <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> of an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a>, prioritized by their <a href="Degree_(graph_theory)" title="Degree (graph theory)">degrees</a>, and repeatedly find and remove the vertex of minimum degree.<a href="#cite_note-skiena-1">[1]</a> This <a href="Greedy_algorithm" title="Greedy algorithm">greedy algorithm</a> can be used to calculate the <a href="Degeneracy_(graph_theory)" title="Degeneracy (graph theory)">degeneracy</a> of a given graph, equal to the largest degree of any vertex at the time of its removal. The algorithm takes <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>, with or without the optimization that maintains a lower bound on the minimum priority, because each vertex is found in time proportional to its degree and the sum of all vertex degrees is linear in the number of edges of the graph.<a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading3"><h3 id="Dial's_algorithm_for_shortest_paths">Dial's algorithm for shortest paths</h3></div>

In Dijkstra's algorithm for <a href="Shortest_path" class="mw-redirect" title="Shortest path">shortest paths</a> in <a href="Directed_graph" title="Directed graph">directed graphs</a> with edge weights that are positive integers, the priorities are monotone,<a href="#cite_note-varghese-13">[13]</a> and a monotone bucket queue can be used to obtain a time bound of O(m + dc), where m is the number of edges, d is the diameter of the network, and c is the maximum (integer) link cost.<a href="#cite_note-bertsekas-9">[9]</a><a href="#cite_note-festa-14">[14]</a> This variant of Dijkstra's algorithm is also known as <a href="Dial's_algorithm" class="mw-redirect" title="Dial's algorithm">Dial's algorithm</a>,<a href="#cite_note-bertsekas-9">[9]</a> after Robert B. Dial, who published it in 1969.<a href="#cite_note-dial-7">[7]</a> The same idea also works, using a quantized bucket queue, for graphs with positive real edge weights when the ratio of the maximum to minimum weight is at most c.<a href="#cite_note-15">[15]</a> In this quantized version of the algorithm, the vertices are processed out of order, compared to the result with a non-quantized priority queue, but the correct shortest paths are still found.<a href="#cite_note-pseudo-5">[5]</a> In these algorithms, the priorities will only span a range of width c + 1, so the modular optimization can be used to reduce the space to O(n + c).<a href="#cite_note-ms-8">[8]</a><a href="#cite_note-festa-14">[14]</a>

A variant of the same algorithm can be used for the <a href="Widest_path_problem" title="Widest path problem">widest path problem</a>. In combination with methods for quickly partitioning non-integer edge weights into subsets that can be assigned integer priorities, it leads to near-linear-time solutions to the single-source single-destination version of the widest path problem.<a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading3"><h3 id="Greedy_set_cover">Greedy set cover</h3></div>

The <a href="Set_cover_problem" title="Set cover problem">set cover problem</a> has as its input a <a href="Family_of_sets" title="Family of sets">family of sets</a>. The output should be a subfamily of these sets, with the same union as the original family, including as few sets as possible. It is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, but has a <a href="Set_cover_problem#Greedy_algorithm" title="Set cover problem">greedy approximation algorithm</a> that achieves a logarithmic approximation ratio, essentially the best possible unless <a href="P_versus_NP_problem" title="P versus NP problem">P = NP</a>.<a href="#cite_note-17">[17]</a> This approximation algorithm selects its subfamily by repeatedly choosing a set that covers the maximum possible number of remaining uncovered elements.<a href="#cite_note-18">[18]</a> A standard exercise in algorithm design asks for an implementation of this algorithm that takes linear time in the input size, which is the sum of sizes of all the input sets.<a href="#cite_note-19">[19]</a>

This may be solved using a bucket queue of sets in the input family, prioritized by the number of remaining elements that they cover. Each time that the greedy algorithm chooses a set as part of its output, the newly covered set elements should be subtracted from the priorities of the other sets that cover them; over the course of the algorithm the number of these changes of priorities is just the sum of sizes of the input sets. The priorities are monotonically decreasing integers, upper-bounded by the number of elements to be covered. Each choice of the greedy algorithm involves finding the set with the maximum priority, which can be done by scanning downwards through the buckets of the bucket queue, starting from the most recent previous maximum value. The total time is linear in the input size.<a href="#cite_note-lmw-10">[10]</a>

<div class="mw-heading mw-heading3"><h3 id="Scheduling">Scheduling</h3></div>

Bucket queues can be used to schedule tasks with deadlines, for instance in <a href="Packet_forwarding" title="Packet forwarding">packet forwarding</a> for internet data with <a href="Quality_of_service" title="Quality of service">quality of service</a> guarantees. For this application, the deadlines should be quantized into discrete intervals, and tasks whose deadlines fall into the same interval are considered to be of equivalent priority.<a href="#cite_note-figueira-2">[2]</a>

A variation of the quantized bucket queue data structure, the <a href="Calendar_queue" title="Calendar queue">calendar queue</a>, has been applied to scheduling of <a href="Discrete-event_simulation" title="Discrete-event simulation">discrete-event simulations</a>, where the elements in the queue are future events prioritized by the time within the simulation that the events should happen. In this application, the ordering of events is critical, so the priorities cannot be approximated. Therefore, the calendar queue performs searches for the minimum-priority element in a different way than a bucket queue: in the bucket queue, any element of the first non-empty bucket may be returned, but instead the calendar queue searches all the elements in that bucket to determine which of them has the smallest non-quantized priority. To keep these searches fast, this variation attempts to keep the number of buckets proportional to the number of elements, by adjusting the scale of quantization and rebuilding the data structure when it gets out of balance. Calendar queues may be slower than bucket queues in the worst case (when many elements all land in the same smallest bucket) but are fast when elements are uniformly distributed among buckets causing the average bucket size to be constant.<a href="#cite_note-20">[20]</a><a href="#cite_note-21">[21]</a>

<div class="mw-heading mw-heading3"><h3 id="Fast_marching">Fast marching</h3></div>

In <a href="Applied_mathematics" title="Applied mathematics">applied mathematics</a> and <a href="Numerical_method" title="Numerical method">numerical methods</a> for the solution of <a href="Differential_equation" title="Differential equation">differential equations</a>, untidy priority queues have been used to prioritize the steps of the <a href="Fast_marching_method" title="Fast marching method">fast marching method</a> for solving <a href="Boundary_value_problem" title="Boundary value problem">boundary value problems</a> of the <a href="Eikonal_equation" title="Eikonal equation">Eikonal equation</a>, used to model <a href="Wave_propagation" class="mw-redirect" title="Wave propagation">wave propagation</a>. This method finds the times at which a moving boundary crosses a set of discrete points (such as the points of an integer grid) using a prioritization method resembling a continuous version of <a href="Dijkstra" title="Dijkstra">Dijkstra</a>'s algorithm, and its running time is dominated by its priority queue of these points. It can be sped up to linear time by rounding the priorities used in this algorithm to integers, and using a bucket queue for these integers. As in Dijkstra's and Dial's algorithms, the priorities are monotone, so fast marching can use the monotone optimization of the bucket queue and its analysis. However, the discretization introduces some error into the resulting calculations.<a href="#cite_note-remarks-4">[4]</a>

<ul><li><a href="Soft_heap" title="Soft heap">Soft heap</a>, a different way of speeding up priority queues by using approximate priorities</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSkiena1998" class="citation cs2"><a href="Steven_Skiena" title="Steven Skiena">Skiena, Steven S.</a> (1998), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=TrXd-gxPhVYC&pg=PA181">The Algorithm Design Manual</a>, Springer, p. 181, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780387948607</bdi></cite>.

</li>

<li id="cite_note-figueira-2">^ <a href="#cite_ref-figueira_2-0">a</a> <a href="#cite_ref-figueira_2-1">b</a> <a href="#cite_ref-figueira_2-2">c</a> <cite id="CITEREFFigueira1997" class="citation cs2">Figueira, N. R. (1997), "A solution for the priority queue problem of deadline-ordered service disciplines", Proceedings of Sixth International Conference on Computer Communications and Networks, IEEE Computer Society Press, pp. 320–325, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ficccn.1997.623330">10.1109/icccn.1997.623330</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-8186-1</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5611516">5611516</a></cite>

</li>

<li id="cite_note-hns-3">^ <a href="#cite_ref-hns_3-0">a</a> <a href="#cite_ref-hns_3-1">b</a> <cite id="CITEREFHenzingerNoeSchulz2019" class="citation cs2"><a href="Monika_Henzinger" title="Monika Henzinger">Henzinger, Monika</a>; Noe, Alexander; Schulz, Christian (2019), "Shared-memory exact minimum cuts", 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019, pp. 13–22, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1808.05458">1808.05458</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FIPDPS.2019.00013">10.1109/IPDPS.2019.00013</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-7281-1246-6</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52019258">52019258</a></cite>

</li>

<li id="cite_note-remarks-4">^ <a href="#cite_ref-remarks_4-0">a</a> <a href="#cite_ref-remarks_4-1">b</a> <a href="#cite_ref-remarks_4-2">c</a> <cite id="CITEREFRaschSatzger2009" class="citation cs2">Rasch, Christian; Satzger, Thomas (2009), <a rel="nofollow" class="external text" href="https://pcbornemann4.ma.tum.de/foswiki/pub/M3/Allgemeines/Publications/drm028v1.pdf">"Remarks on the O(N) implementation of the fast marching method"</a> (PDF), IMA Journal of Numerical Analysis, 29 (3): 806–813, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fimanum%2Fdrm028">10.1093/imanum/drm028</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2520171">2520171</a></cite>

</li>

<li id="cite_note-pseudo-5">^ <a href="#cite_ref-pseudo_5-0">a</a> <a href="#cite_ref-pseudo_5-1">b</a> <cite id="CITEREFRobledoGuivant2010" class="citation cs2">Robledo, Alicia; Guivant, José E. (2010), <a rel="nofollow" class="external text" href="https://www.araa.asn.au/acra/acra2010/papers/pap144s1-file1.pdf">"Pseudo priority queues for real-time performance on dynamic programming processes applied to path planning"</a> (PDF), in Wyeth, Gordon; Upcroft, Ben (eds.), Australasian Conference on Robotics and Automation</cite>

</li>

<li id="cite_note-es-6">^ <a href="#cite_ref-es_6-0">a</a> <a href="#cite_ref-es_6-1">b</a> <cite id="CITEREFEdelkampSchroedl2011" class="citation cs2">Edelkamp, Stefan; Schroedl, Stefan (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=3k5MVjKzBP4C&pg=PA90">"3.1.1 Bucket Data Structures"</a>, Heuristic Search: Theory and Applications, Elsevier, pp. 90–92, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780080919737</bdi></cite>. See also p. 157 for the history and naming of this structure.

</li>

<li id="cite_note-dial-7">^ <a href="#cite_ref-dial_7-0">a</a> <a href="#cite_ref-dial_7-1">b</a> <a href="#cite_ref-dial_7-2">c</a> <cite id="CITEREFDial1969" class="citation cs2">Dial, Robert B. (1969), "Algorithm 360: Shortest-path forest with topological ordering [H]", <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>, 12 (11): 632–633, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F363269.363610">10.1145/363269.363610</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6754003">6754003</a></cite>.

</li>

<li id="cite_note-ms-8">^ <a href="#cite_ref-ms_8-0">a</a> <a href="#cite_ref-ms_8-1">b</a> <a href="#cite_ref-ms_8-2">c</a> <cite id="CITEREFMehlhornSanders2008" class="citation cs2"><a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, Kurt</a>; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</a> (2008), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=oK3UWxg_UhsC&pg=PA201">"10.5.1 Bucket Queues"</a>, Algorithms and Data Structures: The Basic Toolbox, Springer, p. 201, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540779773</bdi></cite>.

</li>

<li id="cite_note-bertsekas-9">^ <a href="#cite_ref-bertsekas_9-0">a</a> <a href="#cite_ref-bertsekas_9-1">b</a> <a href="#cite_ref-bertsekas_9-2">c</a> <a href="#cite_ref-bertsekas_9-3">d</a> <cite id="CITEREFBertsekas1991" class="citation cs2"><a href="Dimitri_Bertsekas" title="Dimitri Bertsekas">Bertsekas, Dimitri P.</a> (1991), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7i3XQVNkJqIC&pg=PA72">"Dial's algorithm"</a>, Linear Network Optimization: Algorithms And Codes, Cambridge, Massachusetts: MIT Press, pp. 72–75, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-02334-2</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1201582">1201582</a></cite>

</li>

<li id="cite_note-lmw-10">^ <a href="#cite_ref-lmw_10-0">a</a> <a href="#cite_ref-lmw_10-1">b</a> <cite id="CITEREFLimMoffatWirth2014" class="citation cs2">Lim, C. L.; Moffat, Alistair; Wirth, Anthony Ian (2014), <a rel="nofollow" class="external text" href="https://crpit.scem.westernsydney.edu.au/abstracts/CRPITV147Lim.html">"Lazy and eager approaches for the set cover problem"</a>, in Thomas, Bruce; Parry, Dave (eds.), Thirty-Seventh Australasian Computer Science Conference, ACSC 2014, Auckland, New Zealand, January 2014, CRPIT, vol. 147, Australian Computer Society, pp. 19–27</cite>. See in particular Section 2.4, "Priority Queue", p. 22.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFJohnson1981" class="citation cs2"><a href="Donald_B._Johnson" title="Donald B. Johnson">Johnson, Donald B.</a> (1981), "A priority queue in which initialization and queue operations take O(log log D) time", <a href="Mathematical_Systems_Theory" class="mw-redirect" title="Mathematical Systems Theory">Mathematical Systems Theory</a>, 15 (4): 295–309, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01786986">10.1007/BF01786986</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0683047">0683047</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:35703411">35703411</a></cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFMatulaBeck1983" class="citation cs2"><a href="David_Matula" title="David Matula">Matula, David W.</a>; Beck, L. L. (1983), "Smallest-last ordering and clustering and graph coloring algorithms", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 30 (3): 417–427, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2402.322385">10.1145/2402.322385</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0709826">0709826</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4417741">4417741</a></cite>.

</li>

<li id="cite_note-varghese-13"><a href="#cite_ref-varghese_13-0">^</a> <cite id="CITEREFVarghese2005" class="citation cs2"><a href="George_Varghese" title="George Varghese">Varghese, George</a> (2005), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=fnZ9WWpVK7oC&pg=PA78">Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices</a>, Morgan Kaufmann, pp. 78–80, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780120884773</bdi></cite>.

</li>

<li id="cite_note-festa-14">^ <a href="#cite_ref-festa_14-0">a</a> <a href="#cite_ref-festa_14-1">b</a> <cite id="CITEREFFesta2006" class="citation cs2">Festa, Paola (2006), "Shortest path algorithms", in <a href="Mauricio_Resende" title="Mauricio Resende">Resende, Mauricio G. C.</a>; <a href="Panos_M._Pardalos" title="Panos M. Pardalos">Pardalos, Panos M.</a> (eds.), Handbook of Optimization in Telecommunications, Boston: Springer, pp. 185–210, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-30165-5_8">10.1007/978-0-387-30165-5_8</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-30662-9</bdi></cite>; see in particular Section 8.3.3.6, "Dial's implementation", pp. 194–195.

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="#CITEREFMehlhornSanders2008">Mehlhorn & Sanders (2008)</a> (Exercise 10.11, p. 201) credit this idea to a 1978 paper of E. A. Dinic (Yefim Dinitz).

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFGabowTarjan1988" class="citation cs2"><a href="Harold_N._Gabow" title="Harold N. Gabow">Gabow, Harold N.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1988), <a rel="nofollow" class="external text" href="https://zenodo.org/record/1258419">"Algorithms for two bottleneck optimization problems"</a>, Journal of Algorithms, 9 (3): 411–417, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2888%2990031-4">10.1016/0196-6774(88)90031-4</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0955149">0955149</a></cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFDinurSteurer2014" class="citation cs2"><a href="Irit_Dinur" title="Irit Dinur">Dinur, Irit</a>; Steurer, David (2014), "Analytical approach to parallel repetition", in <a href="David_Shmoys" title="David Shmoys">Shmoys, David B.</a> (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, ACM, pp. 624–633, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1305.1979">1305.1979</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2591796.2591884">10.1145/2591796.2591884</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2710-7</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3238990">3238990</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15252482">15252482</a></cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFJohnson1974" class="citation cs2"><a href="David_S._Johnson" title="David S. Johnson">Johnson, David S.</a> (1974), "Approximation algorithms for combinatorial problems", <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>, 9 (3): 256–278, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2874%2980044-9">10.1016/S0022-0000(74)80044-9</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0449012">0449012</a></cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFCormenLeisersonRivestStein2009" class="citation book cs2"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2009) [1990], "Exercise 35.3-3", <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a> (3rd ed.), MIT Press and McGraw-Hill, p. 1122, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03384-4</bdi></cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFBrown1988" class="citation cs2">Brown, R. (October 1988), "Calendar queues: a fast <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> priority queue implementation for the simulation event set problem", <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>, 31 (10): 1220–1227, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F63039.63045">10.1145/63039.63045</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:32086497">32086497</a></cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFEricksonLadnerLaMarca2000" class="citation cs2">Erickson, K. Bruce; <a href="Richard_E._Ladner" title="Richard E. Ladner">Ladner, Richard E.</a>; LaMarca, Anthony (2000), "Optimizing static calendar queues", ACM Transactions on Modeling and Computer Simulation, 10 (3): 179–214, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F361026.361028">10.1145/361026.361028</a></cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-10" href="https://en.wikipedia.org/wiki/?title=Bucket_queue&oldid=1268544136">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>